package head;

public class a239_滑动窗口最大值 {
//    每轮循环：
//    判断队头元素是不是已经超出窗口范围，超出则去掉。
//    将比当前数值小的值全部去掉。
//    插入当前数值。
//    如果当前窗口已经达到了kk的大小，就开始输出队首元素（当前窗口最大值）。
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] q = new int[100010];
        int hh = 0, tt = -1;
        int[] res = new int[nums.length - k + 1];
        for (int i = 0, j = 0; i < nums.length; i++) {
            if (tt >= hh && q[hh] < i - k + 1) hh++;
            while (tt >= hh && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            if (i >= k - 1) res[j++] = nums[q[hh]];
        }
        return res;
    }

}
